import java.util.Arrays;
import java.util.Stack;

public class QuickSortNonRecursion {
    public static void quickSort(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partiton(array,left,right);
        if(pivot > left+1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot < right -1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partiton(array,left,right);
            if(pivot>left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot<right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
    public static int partiton(int[] array,int start,int end){
        int tmp = array[start];
        while(start<end){
            while(start<end && array[end] >=tmp){
                end--;
            }
            array[start] = array[end];
            while (start<end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

    public static void main(String[] args) {
        int[] array = {12,5,8,1,10,15};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
